package HashTable._380_InsertDeleteGetRandom;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

public class RandomizedSet {
    /** Initialize your data structure here. */
    HashMap<Integer,Integer> vals;
    List<Integer> list;

    public RandomizedSet() {
        vals = new HashMap<>();
        list = new ArrayList<>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(vals.containsKey(val)) return false;
        list.add(val);
        vals.put(val, list.size() - 1);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        int id = vals.getOrDefault(val, -1);
        if (id == -1) {
            return false;
        }
        Collections.swap(list, id, list.size() - 1);
        int swapWith = list.get(id);
        //update the swapwith's value
        vals.put(swapWith, id);
        list.remove(list.size() - 1);
        vals.remove(val);
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        int max = list.size();
        int min = 0;
        int id = (int) (Math.random() * (max - min) + min);
        return list.get(id);
    }
}
